home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000118_icon-group-sender _Wed Dec 15 15:46:59 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  3KB
  1. Received: by cheltenham.cs.arizona.edu; Wed, 15 Dec 1993 18:26:11 MST
  2. Message-Id: <9312152344.AA26970@enlil.premenos.sf.ca.us>
  3. From: Ken Walker <kwalker@shara.premenos.sf.ca.us>
  4. Subject: Re: Need help with (simple?) programming problem.
  5. To: icon-group@cs.arizona.edu
  6. Date: Wed, 15 Dec 93 15:46:59 PST
  7. Mailer: Elm [revision: 66.25]
  8. Status: R
  9. Errors-To: icon-group-errors@cs.arizona.edu
  10.  
  11. > From Ronal F. Guilmette:
  12. >
  13. > Assume that I have three strings, i.e. "red ", "green ", and "blue ". Now
  14. > I want to create a generator which will successively yield each unique
  15. > string which contains no more than one instance of each of the original
  16. > strings.  Here are the string values which should be yielded by the various
  17. > invocations/resumptions of the generator:
  18. > 
  19. >         ""
  20. >         "red "
  21. >         "green "
  22. >         "blue "
  23. >         "red green "
  24. >         "red blue "
  25. >         "green red "
  26. >         "green blue "
  27. >         "blue red "
  28. >         "blue green "
  29. >         "red green blue "
  30. >         "red blue green "
  31. >         "green red blue "
  32. >         "green blue red "
  33. >         "blue red green "
  34. >         "blue green red "
  35. > 
  36. > After being invoked/resumed 16 times (and yielding each of the above strings
  37. > once) the generator should fail.  Note that the actual *order* in which the
  38. > above strings are yielded is totally unimportant.  Any order will do as long
  39. > as I get these 16 strings (eventually).
  40. > 
  41. > Also note that the ORDER in which the original strings appear in the genera-
  42. > ted strings *is* significant.
  43.  
  44. I found the hard part was formulating the problem in "constructive"
  45. terms. The problem, as I understand it, is to generate all the permutaions
  46. of all the subsets of a list of words. Once it is formulated that way,
  47. it is simple to solve using two recursive generators (permutaions has
  48. certainly been done using this technique before, and I suspect subsets
  49. has also). Here is a solution using list invocation:
  50.  
  51.    procedure main()
  52.       p("red", "blue", "green")
  53.    end
  54.    
  55.    procedure p(words[])
  56.       every write(permute ! (subsets ! words))
  57.    end
  58.    
  59.    procedure subsets(words[])
  60.       local i, w, tail
  61.    
  62.       suspend []
  63.       every i := 1 to *words do {
  64.          w := words[i : i + 1]
  65.          tail := words[i + 1 : 0]
  66.          suspend w ||| (subsets ! tail)
  67.          }
  68.    end
  69.    
  70.    procedure permute(words[])
  71.       local i, head, w, tail
  72.    
  73.       if *words = 0 then
  74.         return ""
  75.       every i := 1 to *words do {
  76.          head := words[1 : i] 
  77.          w := words[i] 
  78.          tail := words[i + 1 : 0]
  79.          suspend w || " " || (permute ! (head ||| tail))
  80.          }
  81.    end
  82.    
  83.    
  84. Ken Walker, kwalker@premenos.sf.ca.us
  85.  
  86.